#ifndef lfstack_h__
#define lfstack_h__
#include "atomic.h"
#include "criticalsection.h"
#include "debug/assert.h"

namespace gecko
{

// a lock-free stack.
// fast, non-blocking stack for thread safe stack operations.
template<typename T>
class LFStack
{
public:
	// a stack node.
	class Node
    {
	public:
		// pointer to the next node in the stack.
        Node* Next;

		// the data contained in the node.
        T Data;
    };

    // construct empty stack.
    LFStack();

    // destructor.
    virtual ~LFStack();

    // push operation.
    void Push(const T& item);

    // pop operation.
	// returns pointer to node which has been removed.  Returns NULL if empty.
    Node* Pop();

    // clear the stack.
    void Clear();

private:

    Node* m_Head;

#if defined(ENABLE_CRITICAL_SECTION)
	CriticalSection m_critSection;
#endif
};

template<typename T>
LFStack<T>::LFStack()
{
    m_Head = 0;
}

template<typename T>
LFStack<T>::~LFStack()
{
    gtAssert(Debug::MsgFilters::Containers, m_Head == 0, "Trying to delete a stack which is not empty");
}

template<typename T>
void LFStack<T>::Clear()
{
	Node* node = Pop();
	while ( node )
	{
		delete node;
		node = Pop();
	};

	m_Head = 0;
}

template<typename T>
void LFStack<T>::Push(const T& item)
{
#if defined(ENABLE_CRITICAL_SECTION)
	m_critSection.Begin();
#endif

    Node* node = new Node;
    node->Data = item;

    bool updatedLinks = false;
    while ( !updatedLinks )
    {
		volatile Node** vtop =  (volatile Node**)&m_Head;
		volatile Node* vnode = (volatile Node*)node;
        volatile Node* current = *vtop;
        vnode->Next = (Node*)current;
		updatedLinks = Atomic::CompareSwapPtr((volatile void**)vtop, (void*)current, (void*)vnode);
    };

#if defined(ENABLE_CRITICAL_SECTION)
	m_critSection.End();
#endif
}

template<typename T>
typename LFStack<T>::Node* LFStack<T>::Pop()
{
#if defined(ENABLE_CRITICAL_SECTION)
	m_critSection.Begin();
#endif

    volatile Node** vtop = (volatile Node**)&m_Head;
	volatile Node* vnode = 0;
	bool updatedLinks = false;
    while ( !updatedLinks )
	{
		vnode = *vtop;
		if ( !vnode )
		{
#if defined(ENABLE_CRITICAL_SECTION)
			m_critSection.End();
#endif
			return 0;
		}

		volatile Node* next = vnode->Next;
		updatedLinks = Atomic::CompareSwapPtr((volatile void**)vtop, (void*)vnode, (void*)next);
	}

#if defined(ENABLE_CRITICAL_SECTION)
	m_critSection.End();
#endif

	return (Node*)vnode;
}

}

#endif
